The basic idea of compressed sensing is to reconstruct a high-dimensional signal from a small number of measurements. The compressive measurements can be thought of as a linear mapping of a signal x0 of length N to a measurement vector y of length M<N. This process can be modeled by a M×N measurement matrix A.
The compressed sensing reconstruction problem is to determine the signal x0 from the measurements y when sampled asy=Ax0+w; wherein w represents the measurement noise.
Compressed sensing asserts that signals can be recovered from fewer samples than dictated by the Shannon-Nyquist theorem if they are sparse, that is, it allows to reconstruct a signal by finding a solution to an underdetermined linear system if the signal is sparse in some transform domain. If the signal x0 is sparse in some transform domain, i.e. x0=Ψξ where ξ is sparse, it can be shown that if Ψ is incoherent with A, then ξ can be recovered when M<N. Ψ represents the inverse transform matrix, for example an inverse Wavelet transform.
Compressed sensing can be used in various applications such as MRI, facial recognition, holography, audio restoration or in mobile phone camera sensors. In a camera sensor, the approach allows e.g. to significantly reduce the acquisition energy per image (or equivalently increase the image frame rate) by capturing only few measurements (e.g. 10%) instead of the whole image. However, this comes at the cost of complex reconstruction algorithms.